package dp.备忘录dfs;

import java.util.HashMap;
import java.util.Map;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 整数替换397.java
 * @createTime 2024年04月02日 17:33:00
 */
public class 整数替换397 {
	Map<Long, Integer> memo = new HashMap<>();

	public int integerReplacement(int n) {
		return dfs(n);
	}

	int dfs(long n) {
		if (n == 1) {
			return 0;
		}
		if (memo.containsKey(n)) {
			return memo.get(n);
		}
		int num = 0;
		if (n % 2 == 0) {
			num = dfs(n / 2) + 1;
		} else {
			num = Math.min(dfs(n - 1), dfs(n + 1)) + 1;
		}
		memo.put(n, num);
		return num;
	}
}
